package leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-13 11:57
 **/
public class LeetCode946 {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int m = pushed.length;

        Deque<Integer> deque = new LinkedList<>();
        int j = 0;
        for (int i = 0; i < m; i++) {
            if (popped[j] == pushed[i]) {
                j++;
                while (deque.size() > 0 && deque.peek() == popped[j]) {
                    deque.pop();
                    j++;
                }
            } else {
                deque.push(pushed[i]);
            }
        }
        return deque.size() > 0 ? false : true;
    }

}
